package 贪心;

import java.util.ArrayList;
import java.util.List;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 用最少的箭引爆气球.java
 * @Description TODO
 * @createTime 2020年10月20日 16:18:00
 * 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。
 *
 * 一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
 *
 * Example:
 *
 * 输入:
 * [[10,16], [2,8], [1,6], [7,12]]
 *
 * 输出:
 * 2
 *
 * 解释:
 * 对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。
 *
 * 思路：如果两个有重叠空间就+1 然后删除这个空间
 *      从第一个空间开始遍历 如果有重合的就+1 然后删除这个空间
 *      但这样的思路有问题
 *
 *      题解的思路是先排序用箭来一次次尝试 如果这个箭可以戳破就不要增加 如果不够就增加
 *      先从第一个的右端点开始尝试 如果在下一个的左端点之后则可以一起引爆 如果不行就要加一根箭 在这个过程中要不断维护箭的位置
 *      总结：一端有序 然后比较另一端
 */
public class 用最少的箭引爆气球 {

    //有问题的思路
//    public static void main(String[] args) {
//        int[][] points={{10,16},{2,8},{1,6},{7,12}};
//        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
//        for(int[] a:points){
//            ArrayList<Integer> c=new ArrayList<>();
//            c.add(a[0]);
//            c.add(a[1]);
//            list.add(c);
//        }
//
//        for(int i=0;i<list.size();i++){
//            int a=list.get(i).get(0);
//            int b=list.get(i).get(1);
//            for(int j=i+1;j<list.size();i++){
//                int a1=list.get(j).get(0);
//                int b1=list.get(j).get(1);
//                //有四种情况 j包含i  i包含j   j和i相交 j和i无关
//                if(b<a1||b1<a){
//                    break;
//                }else {
//                    a=Math.min(a,a1);
//                    b=Math.max(b,b1);
//                list.remove(j);
//                }
//
//            }
//        }
//
//        System.out.println(list.size());
//    }



//class Solution {
//    public int findMinArrowShots(int[][] points) {
//        if(points.length==0) return 0;
//        Arrays.sort(points,(a,b)->(a[1]-b[1]));//按照右端点升序排列
//        int tail=points[0][1];
//        int num=1;
//        for(int i=1;i<points.length;i++){
//            if(tail>=points[i][0])
//            continue;
//            tail=points[i][1];
//            num++;
//        }
//        return num;
//    }
//}


}
